package E.哈希表;

import java.util.HashSet;
import java.util.Set;

public class _剑指Offer03_数组中重复的数字 {
    /**
     * 自解：用set存储 如果重复就返回
     * --遍历数组 时间复杂度为n 空间复杂度为n
     *
     * --没有利用0-n-1的思路
     * @param nums
     * @return
     */
    public int findRepeatNumber(int[] nums) {

        Set<Integer> set = new HashSet<>();
        for (int num:nums){
            if (set.contains(num)){
                return num;
            }
            set.add(num);
        }
        return 0;
    }

    /**题解：借助数值是在0-n-1所以 一个萝卜一个坑
     * 从0开始遍历 用index对应的数组值与数组值作为index的数组值做比较判断
     * 如果相等 就返回数组值 否则就交换直到换到自己应该到的坑 循环下一次
     */
    public int findRepeatNumber1(int[] nums) {
        int temp;
        for (int i=0;i< nums.length;i++){
            while (nums[i] != i){
                if (nums[i] == nums[nums[i]]){
                    return nums[i];
                }
                temp = nums[i];
                nums[i] = nums[temp];
                nums[temp] = temp;
            }

        }

        return -1;

    }

}
